package Backtracking;
/*
* 单词搜索
* */
public class Exist79 {
    boolean flag=false;
    public boolean exist(char[][] board, String word) {
        int m=board.length;
        int n=board[0].length;
        boolean[][] visited=new boolean[m][n];
        for (int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dfs(board,word,visited,i,j,0);
            }
        }
        return flag;
    }

    private void dfs(char[][] board, String word, boolean[][] visited,int i,int j,int pos) {
        if(i<0 || i>= board.length || j<0 || j >= board[0].length || visited[i][j] || flag
        || board[i][j]!=word.charAt(pos)){
            return;
        }
        if(pos==word.length()-1){
            flag=true;
            return;
        }

        visited[i][j]=true;

        dfs(board, word, visited, i+1, j,pos+1);
        dfs(board, word, visited, i-1, j,pos+1);
        dfs(board, word, visited, i, j+1,pos+1);
        dfs(board, word, visited, i, j-1,pos+1);
        visited[i][j]=false;

    }
}
